using System;
using System.Collections.Generic;
using Framework.Scripts.MapData;
using UnityEngine;
using Random = System.Random;

namespace Gj
{
    public class MapTools
    {
        public static Vector2Int[] AutoFindNode(int x, int y, Vector2Int start, int maxNode, int findDistance, int prohibitDistance, int random)
        {
            Random r = new Random(random);
            XYMap<bool> map = new XYMap<bool>(x, y);
            map.Set(start, true);
            List<Vector2Int> tmp = new List<Vector2Int>();
            List<Vector2Int> list = new List<Vector2Int>();
            tmp.Add(start);

            while (tmp.Count > 0)
            {
                Vector2Int p = tmp[0];
                tmp.RemoveAt(0);
                list.Add(p);
                Vector2Int[] ll = FindNode(p, findDistance, prohibitDistance, maxNode, r);
                for (int i = 0; i < ll.Length; i++)
                {
                    if (!map.In(ll[i])) continue;
                    var range = HexCube.DistanceRange(ll[i], prohibitDistance);
                    var have = false;
                    for (int j = 0; j < range.Length; j++)
                    {
                        if (!map.In(range[j])) continue;
                        if (map.Get(range[j]))
                        {
                            have = true;
                            break;
                        }
                    }
                    if (have) continue;
                    map.Set(ll[i], true);
                    tmp.Add(ll[i]);
                }
            }
            return list.ToArray();
        }

        public static Vector2Int[] FindNode(Vector2Int node, int max, int min, int num, Random r)
        {
            Vector2Int[] l = new Vector2Int[num];
            for (int i = 0; i < num; i++)
            {
                l[i] = RandomNode(node, max, min, r);
            }

            return l;
        }

        public static Vector2Int RandomNode(Vector2Int node, int max, int min, Random r)
        {
            int x = r.Next(min, max) * (r.Next(0, 2) == 0 ? -1 : 1);
            int y = r.Next(min, max) * (r.Next(0, 2) == 0 ? -1 : 1);
            
            return new Vector2Int(node.x + x, node.y + y);
        }
        
        public static bool C(Vector3 point1, float r1, Vector3 point2, float r2)
        {
            var d = (point1 - point2).magnitude;
            return r1 + r2 >= d;
        }

        public static MapIndex[] Random2(MapGroup group, int number, Random random)
        {
            group.Switch();
            var tmp = new MapIndex[number];
            var index = 0;
            // 4个方向
//            var quadrant = Quadrant.LT | Quadrant.LB | Quadrant.RT | Quadrant.RB;
            while (index < number)
            {
                GenerateMap2(group, random, index % 4, ref tmp, index);
                index++;
            }

            return tmp;
        }

        public static void GenerateMap2(MapGroup group, Random random, int quadrant, ref MapIndex[] r, int index)
        {
            MapUnit tmp;
            MapIndex mapIndex;
            mapIndex = new MapIndex();
            var iKey = random.Next(group.Size());
            mapIndex.Index = iKey;
            if (index == 0)
            {
                mapIndex.Position = Vector3.zero;
            }
            else
            {
                // 随机生成坐标
                mapIndex.Position = new Vector3(random.Next(100), 0, random.Next(100));
                switch (quadrant)
                {
                    case Quadrant.LB:
                        mapIndex.Position.z = mapIndex.Position.z * -1;
                        break;
                    case Quadrant.RT:
                        mapIndex.Position.x = mapIndex.Position.x * -1;
                        break;
                    case Quadrant.RB:
                        mapIndex.Position.x = mapIndex.Position.x * -1;
                        mapIndex.Position.z = mapIndex.Position.z * -1;
                        break;
                }
            }

            // 无已经使用连接点
            mapIndex.link = new List<int>();

            // 随机旋转
            mapIndex.Angle = random.Next(360);
            mapIndex.Rotation = Quaternion.AngleAxis(mapIndex.Angle, Vector3.up);
            group.Find(mapIndex.Index, out tmp);
            mapIndex.node = new Vector3[tmp.node.Length];
            for (var i = 0; i < mapIndex.node.Length; i++)
                mapIndex.node[i] = mapIndex.Rotation * tmp.node[i] + mapIndex.Position;

            r[index] = mapIndex;
            if (index == 0) return;

            // 判断最近的index
            MapIndex latest;
            FindLatest(ref r, index, out latest);
//            Debug.LogFormat("index:{0} L:{1} C:{2}", index, latest.Position, mapIndex.Position);

            var center = latest.Position;
            var times = 0;
            Vector3 selectPoint;
            Vector3 linkPoint;
            // 检测碰撞情况
            while (!Collide(ref group, ref mapIndex, ref latest))
            {
                times++;
                if (times > 5) break;
                FindLatestPoint(ref center, ref mapIndex.node, out selectPoint);
                FindLatestPoint(ref mapIndex.Position, ref latest.node, out linkPoint);
                // 向中心点偏移
                var position = mapIndex.Position - (selectPoint - linkPoint);
                for (var i = 0; i < mapIndex.node.Length; i++)
                    mapIndex.node[i] = mapIndex.node[i] - mapIndex.Position + position;

                mapIndex.Position = position;
//                Debug.LogFormat("index:{0} P:{1}", index, mapIndex.Position);
            }

            Debug.LogFormat("P:{0}, R:{1}", mapIndex.Position, mapIndex.Angle);
            r[index] = mapIndex;
        }

        public static void FindLatest(ref MapIndex[] r, int index, out MapIndex latest)
        {
            var d = -1f;
            var current = r[index];
            latest = r[0];
            for (var i = 0; i < index; i++)
            {
                var distance = Distance(current.Position, r[i].Position);
                if (distance < d || d < 0)
                {
                    latest = r[i];
                    d = distance;
                }
            }
        }

        public static void FindLatestPoint(ref Vector3 center, ref Vector3[] nodes, out Vector3 latest)
        {
            var d = -1f;
            latest = nodes[0];
            for (var i = 0; i < nodes.Length; i++)
            {
                var distance = Distance(center, nodes[i]);
                if (distance < d || d < 0)
                {
                    latest = nodes[i];
                    d = distance;
                }
            }
        }

        public static bool IsPointInPolygon(Vector3 point, Vector3[] polygon)
        {
            var inside = false;

            float pointX = point.x, pointY = point.z;

            float startX, startY, endX, endY;
            var endPoint = polygon[polygon.Length - 1];
            endX = endPoint.x;
            endY = endPoint.z;
            var i = 0;
            while (i < polygon.Length)
            {
                startX = endX;
                startY = endY;
                endPoint = polygon[i++];
                endX = endPoint.x;
                endY = endPoint.z;
                inside ^= (endY > pointY) ^ (startY > pointY) &&
                          pointX - endX < (pointY - endY) * (startX - endX) / (startY - endY);
            }

            return inside;
        }

        public static bool Collide(ref MapGroup group, ref MapIndex first, ref MapIndex second)
        {
            foreach (var node in first.node)
                if (IsPointInPolygon(node, second.node))
                    return true;

            return false;
//            MapUnit firstUnit;
//            MapUnit secondUnit;
//            group.Find(first.Index, out firstUnit);
//            group.Find(second.Index, out secondUnit);
//            
//            var axes = firstUnit.GetAxis(first.Rotation);
//            foreach(var axis in axes)
//            {
//                // 判断投影轴上的投影是否存在重叠，若检测到存在间隙则立刻退出判断，消除不必要的运算。
//                if (Overlaps(axis, first.node, second.node))
//                    return true;
//            }
//
//            axes = secondUnit.GetAxis(second.Rotation);
//            foreach(var axis in axes)
//            {
//                // 判断投影轴上的投影是否存在重叠，若检测到存在间隙则立刻退出判断，消除不必要的运算。
//                if (Overlaps(axis, first.node, second.node))
//                    return true;
//            }
//
//            return false;
        }

        public static bool Overlaps(Vector3 axis, Vector3[] firstNodes, Vector3[] secondNodes)
        {
            var fmax = -1f;
            var fmin = -1f;
            foreach (var node in firstNodes)
            {
                var v = Vector3.Dot(node, axis);
                fmax = fmax < 0 ? v : Math.Max(v, fmax);
                fmin = fmin < 0 ? v : Math.Min(v, fmin);
            }

            var smax = -1f;
            var smin = -1f;
            foreach (var node in secondNodes)
            {
                var v = Vector3.Dot(node, axis);
                smax = smax < 0 ? v : Math.Max(v, smax);
                smin = smin < 0 ? v : Math.Min(v, smin);
            }

            var diff = Math.Abs(fmax - smax);
            return fmax > smax ? fmax - fmin > diff : smax - smin > diff;
        }

        public static MapIndex[] Random(MapGroup group, int number, Random random)
        {
            group.Switch();
            var tmp = new MapIndex[number];
            var index = -1;
            var cleanIndex = index;
            var total = 0;
            // 4个方向
            var quadrant = Quadrant.LT | Quadrant.LB | Quadrant.RT | Quadrant.RB;
            var canLinkList = new List<MapBlock>();
            while (total < number)
            {
                total += GenerateMap(group, random, quadrant, ref tmp, index, ref canLinkList);
                index++;

                // 一圈内进行连接处理
                if (index >= cleanIndex)
                {
                    cleanIndex = total;
                    var e = canLinkList.GetEnumerator();
                    while (e.MoveNext())
                    {
                        // 未固定模块，进行随机摆放
                        var block = e.Current;
                        float angle = random.Next(360);
                        var oldIndex = tmp[block.index];
                        MapUnit oldUnit;
                        group.Find(oldIndex.Index, out oldUnit);
                        var link = oldUnit.node[block.linkIndex];
                        Transform(ref oldIndex, ref block.parentLink, ref link, ref angle);
                    }

                    e.Dispose();
                    canLinkList.Clear();
                }
            }

            return tmp;
        }

        internal static int GenerateMap(MapGroup group, Random random, int quadrant, ref MapIndex[] r, int index,
            ref List<MapBlock> canLinkList)
        {
            MapUnit tmp;
            MapIndex mapIndex;
            var t = 0;
            if (index < 0)
            {
                mapIndex = new MapIndex();
                var i = random.Next(group.Size());
                mapIndex.Index = i;
                mapIndex.Position = Vector3.zero;
                // 无已经使用连接点
                mapIndex.link = new List<int>();

                // 随机旋转
                mapIndex.Angle = random.Next(360);
                mapIndex.Rotation = Quaternion.AngleAxis(mapIndex.Angle, Vector3.up);

                // 加入跟节点
                index = 0;
                r[index] = mapIndex;

                t += 1;
            }
            else
            {
                mapIndex = r[index];
            }

            group.Find(mapIndex.Index, out tmp);

            MapUnit currentUnit;
            for (var i = 0; i < tmp.node.Length; i++)
            {
                if (mapIndex.link.Contains(i)) continue;

                var node = tmp.node[i];
                // 当前坐标：以mapIndex为中心
                var currentNode = RotateRound(node, Vector3.zero, Vector3.up, mapIndex.Angle);

                // 确定连接方向
                var q = UpdateQuadrant(quadrant, currentNode);
                if (q == 0) continue;

                mapIndex.link.Add(i);
                quadrant = quadrant ^ q;
                t += 1;

                var currentIndex = new MapIndex();
                var currentUnitIndex = random.Next(group.Size());
                currentIndex.Index = currentUnitIndex;
                group.Find(mapIndex.Index, out currentUnit);
                r[index + t] = currentIndex;

                // 尝试与前连接点进行组合
                if (canLinkList.Count > 0)
                {
                    // todo 最近连接点
                    var block = canLinkList[canLinkList.Count - 1];
                    if (LinkMap(group, ref r, ref mapIndex, ref block, ref currentIndex, ref currentUnit, q,
                            currentNode))
                    {
                        canLinkList.Remove(block);
                        continue;
                    }
                }

                {
                    // 随机连接点
                    var linkIndex = random.Next(currentUnit.node.Length);
                    var sourceIndex = random.Next(currentUnit.node.Length);
                    var linkCurrent = currentUnit.node[linkIndex];
                    var sourceCurrent = currentUnit.node[sourceIndex];
                    var distance = Distance(linkCurrent, sourceCurrent);
                    var block = MakeBlock(index, currentNode, linkIndex, sourceIndex, index + t, distance);

                    // 加入未连接模块列表
                    canLinkList.Add(block);
                }
            }

            return t;
        }

        // 连接block和unit: 同一个父节点
        public static bool LinkMap(MapGroup group, ref MapIndex[] r, ref MapIndex parent, ref MapBlock block,
            ref MapIndex currentIndex, ref MapUnit currentUnit, byte q, Vector3 tNode)
        {
            int first;
            int second;
            var distance = CanLink(ref block, ref currentUnit, out first, out second);
            if (distance > 0)
            {
                var oldIndex = r[block.index];
                MapUnit oldUnit;
                group.Find(oldIndex.Index, out oldUnit);
                var link = oldUnit.node[block.linkIndex];
                var source = block.parentLink - link + oldUnit.node[block.sourceIndex];

                // 求交点
                var insect = Insect(q, block.parentLink, Distance(block.parentLink, source), tNode, distance);

                // 求依赖模块的坐标
                {
                    var angle = Angle(ref block.parentLink, source, ref insect);
                    Transform(ref oldIndex, ref block.parentLink, ref link, ref angle);
                    oldIndex.link.Add(block.sourceIndex);
                }

                // 求当前模块的坐标
                {
                    var linkCurrent = currentUnit.node[first];
                    var sourceCurrent = currentUnit.node[second];
                    var angle = Angle(ref tNode, tNode - linkCurrent + sourceCurrent, ref insect);
                    Transform(ref currentIndex, ref tNode, ref linkCurrent, ref angle);
                }
                currentIndex.link = new List<int> { first, second };
                return true;
            }

            return false;
        }

        // 判断节点在当前角度时所在的象限
        public static byte UpdateQuadrant(int quadrant, Vector3 tNode)
        {
            if ((quadrant & Quadrant.LT) > 0 && tNode.x > 0 && tNode.z > 0)
                return Quadrant.LT;
            if ((quadrant & Quadrant.RT) > 0 && tNode.x < 0 && tNode.z > 0)
                return Quadrant.RT;
            if ((quadrant & Quadrant.LB) > 0 && tNode.x > 0 && tNode.z < 0)
                return Quadrant.LB;
            if ((quadrant & Quadrant.RB) > 0 && tNode.x < 0 && tNode.z < 0)
                return Quadrant.RB;
            return 0;
        }

        public static MapBlock MakeBlock(int parentIndex, Vector3 tNode, int linkIndex, int sourceIndex, int index,
            float distance)
        {
            var block = new MapBlock();
            block.sourceIndex = sourceIndex;
            block.linkIndex = linkIndex;
            block.parentLink = tNode;
            block.index = index;

            // 计算最大最小
            block.max = (float)(distance * 1.5);
            block.min = (float)(distance * 0.5);

            return block;
        }

        // 找寻模块连接点
        public static float CanLink(ref MapBlock first, ref MapUnit second, out int link, out int target)
        {
            // 任意2连接点之间点距离
            for (var i = 0; i < second.node.Length; i++)
            for (var j = 1; j < second.node.Length; j++)
            {
                if (i == j) continue;
                var distance = Distance(second.node[i], second.node[j]);
                if (distance > first.min && distance < first.max)
                {
                    link = i;
                    target = j;
                    return distance;
                }
            }

            link = -1;
            target = -1;
            return 0;
        }

        // 2个圆相交，求交点
        public static Vector3 Insect(byte quadrant, Vector3 point1, float r1, Vector3 point2, float r2)
        {
            var distance = Distance(point1, point2);
            double a = (r1 * r1 - r2 * r2 + distance * distance) / (distance * 2); //圆交点的弦与圆心连线交点 到A圆的圆心距离
            var Ex = point1.x + a * (point2.x - point1.x) / distance; //圆交点的弦与圆心连线交点 X坐标
            var Ey = point1.z + a * (point2.z - point1.z) / distance; //圆交点的弦与圆心连线交点 Y坐标
            var h = Math.Sqrt(r1 * r1 - a * a); //圆交点的弦与圆心连线交点 到圆交点的距离
            var z = h / distance; //比率
            if (distance < r1 + r2 && distance > Math.Abs(r1 - r2)) //正常有两个交点的情况
            {
                var first = new Vector3((int)(Ex - z * (point2.z - point1.z)), 0,
                    (int)(Ey + z * (point2.x - point2.x)));
                var second = new Vector3((int)(Ex + z * (point2.z - point1.z)), 0,
                    (int)(Ey - z * (point2.x - point2.x)));
                switch (quadrant)
                {
                    case Quadrant.LT:
                        return first.z > second.z || first.x > second.x ? first : second;
                    case Quadrant.LB:
                        return first.z < second.z || first.x > second.x ? first : second;
                    case Quadrant.RT:
                        return first.z > second.z || first.x < second.x ? first : second;
                    case Quadrant.RB:
                        return first.z < second.z || first.x < second.x ? first : second;
                    default:
                        return first;
                }
            }

            return Vector3.zero;
        }

        /**
         * 求通过link旋转，将source移动到target的角度
         */
        public static float Angle(ref Vector3 link, Vector3 source, ref Vector3 target)
        {
            var v1 = link - source;
            var v2 = link - target;
            return Vector3.Angle(v1, v2);
        }

        public static void Transform(ref MapIndex mapIndex, ref Vector3 parentLink, ref Vector3 link, ref float angle)
        {
            mapIndex.Position = parentLink - link;
            mapIndex.Position = RotateRound(mapIndex.Position, parentLink, Vector3.up, angle);
            mapIndex.Angle = angle;
            mapIndex.Rotation = Quaternion.AngleAxis(mapIndex.Angle, Vector3.up);
        }

        public static Vector3 RotateRound(Vector3 position, Vector3 center, Vector3 axis, float angle)
        {
            var point = Quaternion.AngleAxis(angle, axis) * (position - center);
            var resultVec3 = center + point;
            return resultVec3;
        }

        public static float Distance(Vector3 first, Vector3 second)
        {
            return (first - second).magnitude;
        }

        public class Quadrant
        {
            public const byte LT = 1;
            public const byte RT = 2;
            public const byte LB = 4;
            public const byte RB = 8;
        }

        public struct MapIndex
        {
            public int Index;
            public Vector3 Position;
            public Quaternion Rotation;
            public float Angle;
            internal List<int> link;
            internal Vector3[] node;
        }

        public struct MapUnit
        {
            public Vector3[] node;
            public Vector3[] axis;

            public MapUnit(params Vector3[] n)
            {
                node = n;
                axis = new Vector3[node.Length - 1];
//                for (var i = 0; i < node.Length; i++)
//                {
//                    Debug.LogFormat("Unit: {0} P:{1}", i, node[i]);
//                }
            }

            public Vector3[] GetAxis(Quaternion rotation)
            {
                for (var i = 0; i < node.Length - 1; i++)
                    axis[i] = rotation * Vector3.Cross(node[i], node[i + 1]).normalized;

                return axis;
            }
        }

        public class MapGroup
        {
            private bool inited;
            public List<MapUnit> unitList;
            public MapUnit[] units;

            public MapGroup()
            {
                unitList = new List<MapUnit>();
            }

            public void Add(MapUnit unit)
            {
                unitList.Add(unit);
            }

            public void Find(int index, out MapUnit unit)
            {
                if (index >= units.Length) throw new Exception("Index error");

                unit = units[index];
            }

            internal void Switch()
            {
                if (inited) return;
                inited = true;
                units = unitList.ToArray();
                unitList.Clear();
            }

            internal int Size()
            {
                return units.Length;
            }
        }

        public struct MapBlock
        {
            public int index;
            public Vector3 parentLink;
            public int linkIndex;
            public int sourceIndex;
            public float min;
            public float max;
        }
    }
}